20220408-TIL

오늘은 어제 문제를 복습하고, 바로 다음 문제도 풀었다.. (동적계획법은 진짜 ㅜㅠ)

• 어제 풀었던 행렬 곱셈 순서 문제는, 행렬 곱셈 규칙을 잘 살펴봐야 하는 문제였다.
  (점화식 형태에 집착하기보다는, 완전 탐색 풀이부터 생각해봐야겠다는 생각이 들었음..)
• 양팔저울 문제는 ‘재귀를 이용한 배낭 문제 풀이’ 를 변형해서 풀 수 있는 문제였다.
• 처음에는 ‘무게가 i인 구슬을 확인할 수 있는지’ 를 확인하는 식으로 풀어보려 했다.
  (확인할 수 있는 모든 무게를 계산하려면, 2^n 번 이상의 연산이 필요해서 배제했다..)
• 질문 게시판에도 괜찮은 힌트가 없어서, 오늘도 인터넷에 검색해서 풀었다.. (ㅜㅠ)
  (i번째 무게추를 저울(추 or 구슬) 에 올릴 때, 올리지 않을 때를 확인하는 재귀 함수)